package xyz.vopen.leetcode.q494;

/**
 * {@link ElveXu}
 *
 * @author <a href="mailto:iskp.me@gmail.com">Elve.Xu</a>
 * @version ${project.version} - 2020-05-06.
 */
public class ElveXu {

  public static void main(String[] args) {
    int[] nums = {1, 1, 1, 1, 1};
    System.out.println(new ElveXu().findTargetSumWays(nums, 3));
  }

  public int findTargetSumWays(int[] nums, int S) {
    return findTargetSumWays(nums, 0, S);
  }

  public int findTargetSumWays(int[] nums, int start, int S) {
    if (start == nums.length) {
      return S == 0 ? 1 : 0;
    }
    int count = 0;
    count += findTargetSumWays(nums, start + 1, S - nums[start]);
    count += findTargetSumWays(nums, start + 1, S + nums[start]);
    return count;
  }
}
